import java.util.LinkedList;
import java.util.Queue;

public class Solution909 {
    public int snakesAndLadders(int[][] board) {
        Queue<int[]> queue = new LinkedList<>();
        int n = board.length;
        queue.offer(new int[]{1, 0});
        int[] visit = new int[n * n + 1];
        visit[1] = 1;
        while (!queue.isEmpty()) {
            int[] temp = queue.poll();
            for (int i = 1; i <= 6; i++) {
                if (temp[0] + i <= n * n) {
                    int target = cal(board, temp[0] + i);
                    if (visit[target] == 0) {
                        if (target == n * n) {
                            return temp[1] + 1;
                        } else {
                            visit[target] = 1;
                            queue.offer(new int[]{target, temp[1] + 1});
                        }
                    }
                }
            }
        }
        return -1;
    }

    int cal(int[][] board,int t){
        int n=board.length;
        int p=n-(t-1)/n-1;
        int q=(t-1)%n;
        if (p%2!=(n-1)%2){
            q=n-q-1;
        }
        return board[p][q]==-1?t:board[p][q];
    }

    public static void main(String[] args) {
        System.out.println(new Solution909().snakesAndLadders(
                new int[][]{{-1,-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1,-1},
                {-1,35,-1,-1,13,-1},{-1,-1,-1,-1,-1,-1},{-1,15,-1,-1,-1,-1}}));
    }
}
